home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group99a.txt / 000129_icon-group-sender _Tue Jun 8 08:27:08 1999.msg < prev    next >
Internet Message Format  |  2000-09-20  |  2KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id IAA08145
  4.     for icon-group-addresses; Tue, 8 Jun 1999 08:26:59 -0700 (MST)
  5. Message-Id: <199906081526.IAA08145@baskerville.CS.Arizona.EDU>
  6. Delivered-To: icon-group@silliac.cs.arizona.edu
  7. To: icon-group@optima.CS.Arizona.EDU
  8. Date: Tue, 08 Jun 1999 00:23:56 GMT
  9. From: cbbrowne@news.isp.giganews.com (Christopher Browne)
  10. Subject: Re: Find the longest matching substrings
  11. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  12. Status: RO
  13.  
  14. On 4 Jun 1999 11:05:40 -0400, gep2@terabites.com <gep2@terabites.com> wrote:
  15. >If I were going to try to make something like this FAST (and especially if one 
  16. >of the strings were relatively constant) I'd probably want to use a hash (or 
  17. >even direct index?) table pre-computed with the offsets of character substrings 
  18. >(I'd probably use two-character adjacent pairs) in one of those strings;  this 
  19. >would enable stepping rapidly through the second string and quickly finding at 
  20. >least (only just the) plausible candidates for launching more detailed substring 
  21. >compare (and length computation) operations.  This kind of thing would likely be 
  22. >storage-hungry, but that's less of a concern today than it once was.
  23.  
  24. Alternatively, treat the main string as a semi-infinite string
  25. (si-string), and insert pointers to each successive character of the
  26. si-string into a Patricia tree.  Then do a tree walk to find the longest
  27. matches that were found. 
  28. -- 
  29. "Unlike computers, guns don't have Y2K problems..."
  30. cbbrowne@hex.net- <http://www.hex.net/~cbbrowne/computing.html>
  31.